package org.labuladong.动态规划算法.一维DP;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-22:49
 * @Description:
 *
 * 标签：动态规划，贪⼼算法，⼀维动态规划
 * 给你⼀个⾮负整数数组 nums，你最初位于数组的第⼀个位置，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，请你使⽤最少的跳跃次数到达数组的最后⼀个位置（假设你总是可以到达数组的最后⼀个位置）。
 * 示例 1:
 * 输⼊：nums = [2,3,1,1,4]
 * 输出：2
 * 解释：跳到最后⼀个位置的最⼩跳跃数是 2。
 *  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后⼀个位置。
 * @version: 1.0
 */
public class LC_45跳跃游戏II2 {
		public static int maxActivities(int[] nums) {
			int n = nums.length;
			if(n == 0) return 0;

			int[] sums = accumulate(nums);

			// 将索引赋值给每个区间的开始时间
			// 将sums 赋值给每个区间的结束时间

			int[][] intervals = new int[n][2];
			for (int i = 0; i < intervals.length; i++) {
				intervals[i][1] = sums[i];
			}

			// 根据区间的结束时间进行排序
			Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

			/**
			 * //TODO 使用 Comparator.comparingInt 方法时，Java 内部会处理可能的整数溢出问题
			 * Comparator.comparingInt(a -> a[1]) 定义了排序的逻辑：根据每个区间的结束时间（a[1]）进行比较。
			 * 如果一个区间的结束时间小于另一个区间的结束时间，它会被排在前面。
			 * 如果两个区间的结束时间相同，它们的相对顺序会保持不变（因为 Comparator 是稳定的）。
			 * {{1, 2}, {2, 3}, {1, 4}, {3, 5}}
			 */
			int count = 1;// 初始化，至少有一个区间
			int end = intervals[0][1];// 初始化，第一个区间的结束时间
			for(int i = 1; i < n; i++) {
				// 如果当前区间的开始时间大于等于结束时间，则该区间可以加入
				if(sums[i] >= end) {
					count++;
					// 更新结束时间为当前区间的结束时间
					end = intervals[i][1];
				}
			}
			return count;// 返回最多活动数

		}

		private static int[] accumulate(int[] nums) {
			int sumAccumulate = 0;
			int[] sum = new int[nums.length];
			for (int i = 0; i < nums.length; i++) {
				sumAccumulate += nums[i];
				sum[i] = sumAccumulate;
			}
			return sum;
		}

	public static void main(String[] args) {
			int[] nums = {2,3,1,1,4};
		System.out.println(maxActivities(nums));
	}
	}
